1. Field of the Invention
This invention relates to the field of data storage in computer systems, and in particular, to bi-directional, first-in, first-out (FIFO) data storage in computer systems.
2. Background Art
A typical computer system consists of a number of modules or components as shown in FIG. 7. Computer systems typically include a central processing unit (CPU) such as a microprocessor 720. The microprocessor is a program-controlled device that obtains, decodes and executes instructions. The computer system includes program storage components such as read only memory (ROM) 725 for storing program instructions. The computer system also includes data storage components such as random access memory (RAM) 730 and mass memory 710 for storing data. The CPU 720 and the storage components 710, 725 and 730 transfer data over a bus 715.
The computer system typically also includes input/output (I/O) components 740 for connecting external devices such as a keyboard 745 to the microprocessor 720. Special purpose components 735, such as memory management units or co-processors, may also be part of the computer system.
The RAM data storage component 730, also known as a "main memory", is a scarce resource that is dynamically allocated to users, programs or processes. Main memory RAM 730 is typically silicon-based. In many applications, dynamic random access memory (DRAM) is used as the main memory 730. Main memory 730 is "byte" organized. That is, memory is arranged as a sequence of 8-bit bytes and the byte is the smallest unit of information accessed out of the memory. In some implementations, 16-bit words (2 bytes) or 32-bit words (4 bytes) are accessed at one time.
The mass memory 710 stores data on disks and typically employs magnetic, optical, magneto-optical or other types of media for information storage. Due to the capacity and the amount of control required to operate the disks, access times to data are quite slow as compared to microprocessor speeds. Thus, the microprocessor 720 uses a data storage area with a faster access time in the form of main memory RAM 730 as previously described.
The storage capacity of main memory 730 is often much less than that of mass memory 710. Main memory 730 is used to store relatively small amounts of data for current use by the microprocessor 720. The faster access time of main memory 730 is closer to the processing speed of the computer. Therefore, the system can operate at higher speeds than if data in current use is accessed from the disk.
To utilize the unique characteristics of the storage areas 710 and 730, data is transferred from main memory 730 to the mass memory 710 for future use, and from the mass memory 710 to main memory 730 for current use.
To operate the mass memory 710, a disk controller 825 is provided as shown in FIG. 8. Among other functions, the disk controller 825 controls rotation of the disks and positions the read/write heads. The disk controller 825 also manages requests to access the disk 890.
One part of the disk controller 825 is the buffer 840. The buffer 840 provides an "intermediate" storage area before data is written to the disk 890 or transferred from the disk 890 to main memory 710. The buffer 840 is typically smaller than main memory 710 and may be 8 kilobytes up to 1 megabyte. In today's advanced disk drive systems, the buffer 840 may be implemented in DRAM or SRAM. Access to the disk 890 is gained by accessing the disk controller's 825 buffer 840.
Buffer 840 access requests are handled by a buffer manager 830. Buffer 840 access requests originate from a plurality of sources. For example, in one disk controller, the buffer manager 830 handles buffer access requests from four sources. First, a host bus computer 700 may request buffer 840 access via the disk controller's 825 host bus interface 801. Second, the disk controller's 825 disk formatter 860 may also request buffer 840 access in order to transfer data to or from the disk drive. The disk drive's embedded microcontroller 880 may also request access to the buffer 840. The DRAM refresh circuitry 832, if a DRAM buffer is used, can be a fourth source of requests for buffer 840 access.
FIG. 8 shows a simplified block diagram of the disk controller as used in a computer system. The disk controller 825 contains a host bus interface 801 coupled to a FIFO 820. The buffer manager 830 is coupled to the FIFO 820, a FIFO 850 and the buffer 840. A disk formatter 860 is also coupled to the FIFO 850. The host bus interface 801, the disk formatter 860 and the buffer manager 830 operate asynchronously with respect to each other.
Therefore, the FIFO's 820 and 850 allow for efficient data transfer. To illustrate, consider the case of reading data from the disk 890. Without FIFO's 820 and 850, the disk formatter 860 transfers data directly to the buffer 840 via the buffer manager 830. During this time, requests to access the buffer cannot be serviced since the buffer manager 830 is servicing the disk formatter's 860 request. After the disk formatter 860 has filled the buffer 840 with data, the host's 700 request can be serviced by the buffer manager 830. Therefore, the data can be read from the buffer 840 into main memory 710. Thus, the host computer 700 must sit idle until the disk formatter 860 is finished accessing the buffer 840.
If the FIFO's 820 and 850 are used, the buffer manager 830 can multiplex between the host bus interface 801, the disk formatter 860, the embedded microcontroller 880 and the DRAM refresh circuitry 832. The FIFO's 820 and 850 enable the buffer manager 830 to multiplex without causing the host bus interface 801 or disk formatter 860 to suffer delays in servicing their data requests. The FIFO's 820 and 850 also allow the host bus interface 801 and disk formatter 860 to transfer data from or to the buffer 840 simultaneously. In the same example of reading data from the disk, the buffer manager 830 could fill the host bus interface's 801 FIFO 820 with data and then retrieve data from the disk formatter's 860 FIFO 850. Next, the data from the disk formatter's 860 FIFO 850 can be stored in the buffer 840 at the same time the host 700 retrieves the data from the host bus interface's 801 FIFO 820. From the host's 700 and disk formatter's 860 perspective, it appears that each has immediate access to the buffer 840 while suffering minimal delay in response to their data servicing requests. In reality, the buffer manager 830 is multiplexing between (possibly) four sources of request for buffer access: the host bus interface 801, the disk formatter 860, the embedded microcontroller 880 of the disk drive, and the DRAM refresh circuitry 832 (if a DRAM buffer is used).
If a DRAM buffer 840 is used in the disk controller 825, transfers between the buffer 840 and the FIFO 850 can use page mode access techniques. In page mode, data is transferred in blocks or bursts rather than one byte at a time. The number of bytes transferred in a burst is known as the burst length. Page mode can be performed as burst transfers or demand transfers.
In burst transfer mode, the burst length represents the number of bytes that are transferred between the buffer 840 and the FIFO 850. For reads from the FIFO 850, the buffer manager grants the FIFO 850 buffer access when the FIFO 850 contains at least as many bytes as the burst length. For writes to the FIFO 850, the buffer manager 830 does not transfer data to the FIFO 850 until the FIFO 850 has at least as many empty bytes as the burst length.
In demand transfer mode, the burst length represents the maximum number of bytes transferred during one buffer access request. A read from the FIFO 850 to the buffer 840 can occur at any time when the FIFO 850 is not empty. Thus, reads from the FIFO 850 can occur when the FIFO 850 contains at least one data byte. For buffer writes, the buffer manager 830 can initiate a transfer when the FIFO 850 has at least one open byte to store data. The burst length again provides the maximum number of bytes that can be transferred during one request. It follows that the number of bytes read from the FIFO 850 is equal to the smaller of the number of bytes in the FIFO 850 or the burst length. Similarly, the number of bytes written to the FIFO 850 is equal to the smaller of the number of empty bytes in the FIFO 850 or the burst length.
Prior art disk controller-FIFO systems support page mode in both burst and demand transfer modes. However, the burst length is set at a fixed number of bytes. The fixed burst length may not result in the most efficient transfer rate, and may, therefore, produce unnecessary delays due to the introduction of wait states at the host. Thus, data transfer rates as seen by the host are hindered. A programmable burst length allows for optimization of the transfer rate.
In DRAM, data can be thought of as being stored in a two-dimensional grid. The address of the data is composed of two parts: the row address and the column address. To transfer data, first the row address is placed on the DRAM's address bus and strobed, using the RAS (row address strobe) signal, and then the column address is placed on the DRAM's address bus and strobed using the CAS (column address strobe) signal. When doing a read, the DRAM places the data residing at the intersection of the selected row and column on its data bus while CAS is asserted; during a write, it takes the data off its data bus and stores it at the intersection of the selected row and column while CAS is asserted.
When using page mode, the first byte transferred has its row and column address strobed into the DRAM, but succeeding bytes, if they are in the same row, need only have their column addresses strobed in. Having to only strobe the column address can significantly decrease the time to access data from the DRAM. (Thus, if burst length is defined as four bytes, the first byte's row and column address are strobed, but the second, third and fourth bytes only have their column address strobed.)
There is an overhead (i.e., the time to strobe the row address) associated with starting a burst, so that the average time to access a data byte decreases as burst length increases, since average access time=(column address strobe time + (row address strobe time/burst length)). If there were no constraints, one could choose the maximum burst length possible, so as to maximize the data transfer rate. However, the disk controller's buffer manager is constrained by the fact that it must not allow the host and disk FIFO's to overflow or underflow. The flow of data into the disk FIFO during a disk read, or out of the disk FIFO during a disk write, cannot be stopped by the buffer manager, so it services the disk FIFO regularly. If the burst length chosen were too long, then the disk FIFO might overflow or underflow while the buffer manager is servicing a burst at the host FIFO. This imposes a constraint on the burst length. Furthermore, in some cases it is not possible to delay the host transfer process by inserting wait states so that the burst length must be chosen such that the host FIFO does not overflow or underflow.
FIFO's provide data storage for small amounts of data: typically a few bytes. The FIFO gets its name from the manner in which data is written to and read from the storage network. That is, data that is written first in time to the FIFO is the first in time to be read from the FIFO. The FIFO storage capacity is finite. Therefore, data may be written to the FIFO as long as space remains. That is, data may be written to the FIFO as long as it is not full. Conversely, data may be read from the FIFO until there is no data remaining, i.e., until it is empty.
FIG. 1 serves to illustrate the operation of a simple FIFO. Suppose that the goal is to transfer data elements X.sub.1 through X.sub.4 from Area 170 to Area 270 using a FIFO. At time t.sub.o, Area 170 contains elements X.sub.1 through X.sub.4 and the FIFO and Area 270 are empty. At time t.sub.1, element X.sub.1 is written to the FIFO. At time t.sub.2, element X.sub.2 is written to the FIFO. Time t.sub.3 illustrates the situation where X.sub.1 has been read from the FIFO to Area 270. Because X.sub.1 is the first element written to the FIFO (at time t.sub.1), it was also the first to be read from the FIFO. At time t.sub.4, X.sub.2, the second element in time to enter the FIFO, is written to Area 270. Also at time t.sub.4, elements X.sub.3 and X.sub.4 are written to the FIFO and can be read from the FIFO to Area 270. At a final time t.sub.f, all of the elements originally in Area 170 are in Area 270.
To accomplish 16-bit and 8-bit data transfers, prior art FIFO's employ a dual mode technique. That is, in one mode, 16-bit data is processed through the FIFO. After completion of the first 16-bit mode, a second 8-bit mode is initiated and an 8-bit data transfer sequence can be performed. Thus, the prior art FIFO's do not allow mixing of data types within the FIFO.